/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.stack;

import java.util.Stack;

/**
 * <p>
 * 求最大四边形的面积
 * 给定一个整数数组，代表着宽度为1的整数型柱子，从柱子中找出最大四边形的面积。
 * 输入：[2,1,5,6,2,3],
 * 输出：10. [5,6]得到最大四边形面积
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * 2015年5月24日
 */
public class LargestRectangleinHistogram {

    public int largestRectangleArea(int[] height) {
        
        int n = height.length;
        int max = 0;
        //使用栈记录上升的柱子
        Stack<Integer> bars =  new Stack<Integer>();
        bars.add(-1);//为了计算相对距离
        
        for(int i=0;i<n;i++){
            //获得栈头元素
            int prev = bars.peek();
            //压入上升序列的下标
            if(prev<0 || height[i]>height[prev]){
                bars.push(i);
            }else{
                //一旦下降，就开始计算四边形的面积
                prev = bars.pop();
                max = Math.max(max, height[prev]*(i-bars.peek()-1));
                i--;//还不确定当前元素是否在上升序列里
            }
        }
        //计算还未计算的上升序列的面积
        while(bars.peek()!=-1){
            int prev = bars.pop();
            max = Math.max(max, height[prev]*(n-bars.peek()-1));
        }
        return max;
    }
    
    public static void main(String[] args) {
        int[] height = {2,1,5,6,2,3};
        LargestRectangleinHistogram histogram = new LargestRectangleinHistogram();
        System.out.println(histogram.largestRectangleArea(height));
    }
}
